package com.haidechizi.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * <p>
 * <p>
 * 上图为 8 皇后问题的一种解法。
 * <p>
 * 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
 * <p>
 * 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * <p>
 * 示例:
 * <p>
 * 输入: 4
 * 输出: [
 * [".Q..",  // 解法 1
 * "...Q",
 * "Q...",
 * "..Q."],
 * <p>
 * ["..Q.",  // 解法 2
 * "Q...",
 * "...Q",
 * ".Q.."]
 * ]
 * 解释: 4 皇后问题存在两个不同的解法。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/n-queens
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _51_N皇后 {

    // 左，右，上，下，左上，左下，右上，右下
    private int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
    private int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};

    public List<List<String>> solveNQueens(int n) {

        List<List<String>> result = new ArrayList<>();
        int[][] mark = new int[n][n];
        Stack<String> list = new Stack<>();
        generate(0, result, mark, list);

        return result;
    }


    /**
     * 放入皇后之后，填充标记
     *
     * @param x
     * @param y
     * @param mark
     */
    public void putQueue(int x, int y, int[][] mark) {
        mark[x][y] = 1;
        for (int i = 1; i < mark.length; i++) {
            for (int j = 0; j < 8; j++) {
                int nexX = x + i * dx[j];
                int nexY = y + i * dy[j];
                if (nexX >= 0 && nexX < mark.length && nexY >= 0 && nexY < mark.length) {
                    mark[nexX][nexY] = 1;
                }
            }
        }
    }

    public void generate(int k, List<List<String>> result, int[][] mark, Stack<String> stack) {

        if (k == mark.length) {
            result.add(stack);
            return;
        }
        for (int i = 0; i < mark.length; i++) {
            if (mark[k][i] == 0) {
                int[][] temp = mark;
                putQueue(k, i, mark);
                stack.add("Q");

                stack.pop();
                stack.add(".");
                generate(k + 1, result, mark, stack);
            }
        }
    }

    public static void main(String[] args) {
        List<List<String>> result = new _51_N皇后().solveNQueens(4);
        for (List<String> list : result) {
            for (String node : list) {
                System.out.print(node);
            }
            System.out.println();
        }
    }
}
